Security is important and there is a lot to learn. I am reading the book Security in Computing and trying to memorize the RSA algorithm.

Prerequisite Math Knowledge

You must understand the following mathematical principles to understand this algorithm and if you don’t understand these principles, look them up first (I had to look up the last one, the Euler totient function, as I had never heard of it):

• Exponentials
• Prime numbers
• Prime factorization
• Greatest Common Denominator (GCD)
• Modular arithmetic
• Euler totient function

This is also going to have development in mind, so you maybe should also understand: binary, char, bits, ascii, UTF-8, etc..

The book is good. However, it can be quite annoying for me when it shows algorithms using one character variables. This may be the mathematical way but I prefer to use a developer style where variables are named clearly. I need to make sure I understand how RSA works so I am going to write about it.

Here is an example of how they use just one character:

The RSA algorithm uses two keys, d and e, which work in pairs, for decryption and encryption, respectively. A plaintext message P is encrypted to ciphertext C by

C = P^e mod n

The plaintext is recovered by

P = C^d mod n

Because of symmetry in modular arithmetic, encryption and decryption are mutual inverses and commutative. Therefore,

P = C^d mod n = (P^e)^d mod n = (P^d)^e mod n

This relationship means that one can apply the encrypting transformation and then the decrypting one, or the one followed by the encrypting one.¹

I would never write code this way and looking at this, it might leave one who is not an expert wondering what do the variables P, C, d, e, n represent again? And is there a reason P, C are capitalized and d, e, n are lower case? Lets rewrite these with nice developer variable names where the name comments itself based on the what it really is. In the quoted text above each variable is defined clearly except what “mod n” really represents, I had to read on to determine this. Also, where to get the values for each variable is not defined, again, I had to read on to determine this, and this led to more equations to add to the list.These are the equations, in order

Equation List

1. ProductOfPrime1Prime2 = Prime1 * Prime2
2. Totient = (Prime1 – 1) * (Prime2 -1)
3. (Totient * AnyInteger) + 1 = 1 mod Totient
4. EncryptPrime * DecryptPrime = 1 mod Totient
5. EncryptPrime * DecryptPrime = (Totient * AnyInteger) + 1 where (Totient * AnyInteger) + 1 has exactly prime factors
6. CipherText = PlainText^EncryptPrime mod ProductOfPrime1Prime2
7. PlainText = Ciphertext^DecryptPrime mod ProductOfPrime1Prime2
8. PlainText = Ciphertext^DecryptPrime mod ProductOfPrime1Prime2 = (PlainText^EncryptPrime)^DecryptPrime mod ProductOfPrime1Prime2 = (PlainText^DecryptPrime)^EncryptPrime mod n

Some of the values above you get to “choose” or if you were writing this algorithm in code, you would probably not “choose” so much as generate the value at random. So if we get to choose, then lets learn how to choose.

Step 1 – Choose two prime numbers, Prime1 and Prime2 to get the ProductOfPrime1Prime2 variable

So our Equation List above starts out with this simple math equation:

Prime1 * Prime2 = ProductOfPrime1Prime2

Ok, so where do you get Prime1 and Prime2 to start? You simply choose the two primes yourself. Find or generate or a list of primes and choose two. Close your eyes and point or pull them out of a hat. It doesn’t matter just choose two primes numbers.

Of course, there are recommendations for choosing primes in production use. Here are a two basic recommendations:

1. Prime1 and Prime2 should be very large prime numbers, at minimum 100 digits long but as larger is more secure and less efficient.
2. Prime 1 and Prime2 should not be the same prime number

Even though Prime1 and Prime2 should be very large, I want to keep this simple, so for example’s sake, let’s use two primes from the list below:

Primes between 0 and 100.

So we can choose any primes we want, for this example, I will choose these two: 19, 31

ProductOfPrime1Prime2 = Prime1 * Prime2

ProductOfPrime1Prime2  = 19 * 31 = 589

ProductOfPrime1Prime2  = 589

Step 2 – Find the Totient of ProductOfPrime1Prime2

You can search the internet and to study to figure out how to get the totient, but it is pretty easy to get. Totient uses a weird symbol that looks like the letter ‘p’ but is not:

Totient = φ(ProductOfPrime1Prime2)

φ(ProductOfPrime1Prime2) = (Prime1 -1) * (Prime2 – 1)

So I guess you don’t really need to know about a totient, you can just trust me, right? Ok, mathematicians are big on proofs and not just trusting someone so, go learn totient. Anyway,  the equation is as simple as this:

Totient = (Prime1 -1) * (Prime2 – 1)

So we already chose Prime1 as 19 and Prime2 as 31 in Step 1, so we have this:

Totient = (19 – 1) * (31 – 1) = 18*30 = 540

Totient = 540

Step 3 – Get a list of possible integers that result in 1 mod Totient

So we have our third and fourth equations in the Equation List:

EncryptPrime * DecryptPrime = 1 mod Totient

(Totient * AnyInteger) + 1 = 1 mod Totient

Notice that in both equations, the right sides are the same: 1 mod Totient

We get the fifth equation in our Equation List by simply merging these equations three and four:

EncryptPrime * DecryptPrime = (Totient * AnyInteger) + 1 where (Totient * AnyInteger) + 1 has exactly two prime factors

In step 2 we determined the totient is 540, so we have this:

EncryptPrime * DecryptPrime = 1 mod 540

So here is where you need to understand modular arithmetic. There are many possible values that equal 1 mod 540. It is a series. The series can be created with this function:

(Totient * AnyInteger) + 1 = 1 mod Totient

(540 * AnyInteger) + 1 = 1 mod 540

AnyInteger is just what it sounds like, it is any integer:  1, 2, 3, 4, 5, …, 100, …, ∞

540 * 1 + 1 = 541

540 * 2 + 1 = 1081

540 * 3 + 1 = 1621

540 * 4 + 1 = 2161

540 * 5 + 1 = 2701

…

540 * 100 + 1 = 54001

Or we make a list of these possible values that equal 1 mod 540 (which as you can see goes on for infinity)

541, 1081, 1621, 2161, 2701, …, 54001, … , ∞

Step 5 – Choose a 1 mod Totient value with exactly two prime factors: EncryptPrime and DecryptPrime

Now that we have a list, we apply the where clause to it:

{ 541, 1081, 1621, 2161, 2701, …, 54001, …, ∞ } where (Totient * AnyInteger) + 1 has exactly two prime factors

Now is when you need to understand Prime Factorization. There are three possibilities for factors and only the second one matches our where clause.

1. The integer is a prime (has only one factor, itself)
2. The integer has two prime factors
3. The integer has more than two prime factors

So let’s get the factors of the integers in our list.

541 = Prime

1081 = 23 × 47

1621 = Prime

2161 = Prime

2701 = 37 × 73

…

54001 = Prime

So from the short list (and remember the list is infinite, we just selected a few) we have two possible representations of 1 mod Totient.
(We didn’t even see any values with more than two prime factors but don’t worry, with bigger numbers you will find them.)

Here is another place where we get to choose. Once again, close your eyes and point or pull them out of a hat. It doesn’t matter just choose.

Again, there is a recommendation:

1. For EncryptPrime choose a prime larger than (p – 1) or (q – 1).

For this example, I have chosen 37 × 73 even though they don’t meet the above recommendation, however, I can make either EncryptPrime or DecryptPrime, they are interchangable.

So I will make the bigger value EncryptPrime.

EncryptPrime = 73

DecryptPrime = 37

Step 6 – Encrypt

We now have everything we need to Encrypt and Decrypt.

CipherText = PlainText^EncryptPrime mod ProductOfPrime1Prime2

Lets say we have an ascii character ‘A’ or 65. We already know what all the variables except for the CipherText are.

PlainText = 65

EncryptPrime = 73

ProductOfPrime1Prime2 = 589

So lets put these values into our equation. This can be done with a simple calculator.

CipherText = 65⁷³ mod 589 = 179

CipherText = 179

Step 6 – Decrypt

Now lets decrypt this.

PlainText = Ciphertext^DecryptPrime mod ProductOfPrime1Prime2

We already know what all the variables are. Normally the PlainText is not known before hand as it is known in this example.

CipherText = 179

DecryptPrime = 37

ProductOfPrime1Prime2 = 589

Lets put these values into our equation and make sure they return ‘A’ or 65.

PlainText = 179³⁷ mod 589 = 65

PlainText = 65

How does this apply to Public/Private key security (your PC to an HTTPS web server)

It is simple. A public and private key are created on the server. When you hit a web server, the web server sends you the public key.

PublicKey contains: EncryptPrime and ProductOfPrime1Prime2

You are never sent the PrivateKey.

PrivateKey = DecryptPrime and ProductOfPrime1Prime2

This works because you cannot derive EncryptPrime from DecryptPrime and ProductOfPrime1Prime2

You encrypt everything you send to the web server with the PublicKey and they encrypt everything they send you with the PrivateKey. You can decrypt what the server sends you, but only the server can decrypt what you send back. So when you type in your Password into a your bank’s web page, your password is sent encrypted so only the server can decrypt it.

1. Pfleeger, Charles P.; Pfleeger, Shari Lawrence (2007-01-23). Security in Computing (4th Edition) (Kindle Locations 19886-19887). Prentice Hall. Kindle Edition.